1. Field of the Invention.
The present invention relates to a method of converting color values, and, more particularly, to a method of converting color values using a color lookup table as may be used in a fax machine, copier or printer.
2. Description of the Related Art.
A color image is often formed by an array of pixels or dots, with each pixel or dot having multiple color components. In image data produced by an input device such as a scanner, for example, each pixel typically has three color components such as red, green and blue (RGB). Each pixel has three color values ranging between 0 and 255, with each of the color values corresponding to a respective one of the three color components. Although human vision can detect only approximately 100 differences in each axis of three dimensional color perception, more than twice that many levels are required in device colorant values to avoid Mach bands because of nonlinearity between device colorant space and human color perception.
Each dot produced by a printer can also be formed by a combination of three or more color components. However, the printer's color components are often cyan, magenta and yellow (CMY) or cyan, magenta, yellow and black (CMYK), instead of red, green and blue. When printing the image with a printer, it is necessary to convert, for each pixel, each of the input color values into respective output color values in order to accurately reproduce the image color on the print medium.
One known method of converting input color values into output color values is to use a look-up table. In the look-up table, a corresponding set of output equivalent color values is provided for each set of input color values in the look-up table. Due to memory constraints, it is not practical for each of the over sixteen million possible combinations of input color values to be listed in the look-up table. Rather, a "sparse" look-up table is created which includes regularly spaced or intermittent combinations of input color values. For example, if the look-up table includes only combinations of input color values in which each color value is a multiple of eight, the over 16 million possible combinations is reduced to just over 32 thousand possible combinations.
Each component of the input color value, for example, red, green or blue, can be visualized as corresponding to a respective axis in three dimensional space, as shown in FIG. 1. Each axis ranges between 0 and 255. The sparse look-up table can be visualized as a plurality of evenly spaced points within this three dimensional space. Thus, a great majority of the input color values in an image will map into a point within this three dimensional space which does not correspond to one of the entries in the look-up table. Rather, the point will be surrounded by eight points from the look-up table which collectively define a cube in the three dimensional space. Eight points defining such a cube are shown in FIG. 1., with the cube surrounding a point P corresponding to the input color values of a pixel in the image.
The traditional method of assigning output color values to a set of input color values represented by point P is to interpolate between the known output color values of the surrounding eight input look-up table entries. More particularly, trilinear interpolation is performed between the output color values that correspond to each of the eight input color values that define the surrounding cube. However, such trilinear interpolation is very computationally intensive.
On a variety of output devices including many printers, the above color values are not displayed directly. This is because a printer is incapable of displaying as broad a range of color values as the pixels contain. Rather, a printer may only be capable of bi-level output. In such bi-level output, at a certain point on the print medium, a dot of at least one of the color components is either printed, or it is not. A process referred to as "halftoning" is used to convey the color values of the visual image to the print medium with a bi-level output. In halftoning, a dot of a given output color is placed at a given point on the print medium only if the corresponding output color value of the corresponding pixel exceeds a threshold value. Thus, the higher the color values in a certain area of the image, the more dots that are printed on the print medium. The human eye tends to average the printed dots and white spaces together as a shade of a color. Moreover, the various ratios of dots to blank spaces in different areas of the printed display are perceived as being different shades of color, corresponding to the color values of the image.
Bi-level printing based upon a comparison of the color values of each pixel to the same constant threshold value would result in undesirable artifacts in the printed image, however. These artifacts may include abrupt color transitions in areas where color values to one side of a line are below the threshold value, and color values to the other side the line are above the threshold value. To eliminate such artifacts, halftoning can be performed using threshold arrays, error diffusion or other methods, such methods being well known to those skilled in the art. If a threshold array is employed, the single threshold value is replaced by a matrix of various threshold values, a fragmentary portion of which is shown in FIG. 3. Since color values typically have 256 levels ranging between 0 and 255 as discussed above, the threshold matrix can be a sixteen row by sixteen column arrangement of cells, with each cell containing a threshold value ranging between 0 and 255. For ease of illustration, however, only a four cell by four cell fragmentary portion of such a threshold matrix is shown in FIG. 3. In a process called "masking", the threshold matrix can be thought of as being superimposed over the image to be printed, with each cell of the threshold matrix corresponding to a pixel in the image. In order to determine whether to print a dot, the color values of each pixel of the image are compared to the threshold value within the corresponding cell of the threshold matrix. In essence, the color values of the pixel are probabilities indicating the likelihood that a dot will be printed at the corresponding point on the print medium. The threshold matrix is then applied to an adjacent block of pixels, and the process continues until all of the pixels of the image have been masked. Separate dithering can be used for each color component of the image as rendered by the device, such as cyan, magenta and yellow.